/*
 * Board.h
 *
 *  Created on: May 30, 2011
 *      Author: hongyang
 */

#include "../smartgame/SgArrayList.h"
#include "../smartgame/SgPoint.h"
#include "../smartgame/SgBoardConst.h"
#include "../smartgame/SgBoardColor.h"
#include "../smartgame/SgMarker.h"
#include "Setup.h"
#include "Move.h"
#include "Block.h"
#include "Util.h"
#include "../smartgame/SgDebug.h"

#ifndef BOARD_H_
#define BOARD_H_

//static int count;

/** Flags for moves. */
enum GoMoveInfoFlag {
	/** The move was a repetition move. */
	GO_MOVEFLAG_REPETITION,

	/** The move caused self-removal of stones. */
	GO_MOVEFLAG_SUICIDE,

	/** The move captured one or more enemy stones. */
	GO_MOVEFLAG_CAPTURING,

	/** The move was illegal according to the current rules and allow ko
	 settings. */
	GO_MOVEFLAG_ILLEGAL,

	_GO_NU_MOVEFLAG
};

const int GO_MAX_NUM_MOVES = (3 * SG_MAX_SIZE * SG_MAX_SIZE);

const int MAX_BLOCKS = SG_MAX_SIZE * SG_MAX_SIZE * 3 / 2;

const int START = 1;

const int CLIMAX = 2;

const int DENOUMONE = 3;

typedef std::bitset<_GO_NU_MOVEFLAG> MoveInfo;

typedef SgArrayList<SgPoint, GO_MAX_NUM_MOVES> Sequence;

typedef SgArrayList<Block, MAX_BLOCKS> BlockList;

class Board {
public:
	Board();
	~Board();

	void copy(const Board& b);

	const SgBoardConst& getBoardConst() const;

	void init();

	bool isNewPosition() const;

	bool occupied(SgPoint p) const;

	bool isEmpty(SgPoint p) const;

	bool isBorder(SgPoint p) const;

	bool isColor(SgPoint p, int c) const;

	bool isPass(SgPoint p) const;

	bool isValid(SgPoint p) const;

	bool hasNeighbors(SgPoint p, SgBlackWhite c) const;

	bool hasDiagonals(SgPoint p, SgBoardColor c) const;

	bool hasNeigh8(SgPoint p, SgBlackWhite c) const;

	bool hasEmptyNeighbors(SgPoint p) const;

	int size() const;

	/**
	 * 0: empty
	 * 1: black
	 * 2: white
	 */
	int getColor(int x, int y) const;

	SgBlackWhite getColor(SgPoint p) const;

	SgPoint getPoint(int x, int y) const;

	SgBlackWhite toPlay() const;

	int Line(SgPoint p) const;

	const SgPointSet& LineSet(SgGrid line) const;

	int numEmptyNeigh(SgPoint p) const;

	int numEmptyDiagonal(SgPoint p) const;
	/**
	 * include diagonals.
	 */
	int num8EmptyNeigh(SgPoint p) const;

	int numNeigh(SgPoint p, SgBlackWhite player) const;

	int numDiagonal(SgPoint p, SgBlackWhite player) const;

	int num8Neigh(SgPoint p, SgBlackWhite player) const;

	const SgPointSet& all(SgBlackWhite player) const;
	const SgPointSet& allEmpty() const {
		return state.empty;
	}

	SgGrid pos(SgPoint p) const;

	/**
	 * do not allow suicide
	 */
	bool isLegal(SgPoint p, SgBlackWhite c) const;

	void play(Move m);

	/**
	 * may be used in MC.
	 */
	void undo();

	/**
	 * the block (if any) that the point is in.
	 * TODO really 0?
	 */
	Block* anchor(SgPoint p) const;

	bool adjTo(SgPoint p, Block* block) const;

	void checkConsistency() const;
	void checkConsistencyBlock(SgPoint p) const;

	int numStones(SgPoint block) const;
	int numLibs(SgPoint block) const;

	bool lastMoveInfo(GoMoveInfoFlag flag) const;
	bool lastMoveSingle() const;
	bool lastMoveMerge() const;
	const SgArrayList<Block*, 4>& getMerged() const;
	const SgArrayList<Block*, 4>& getKilled() const {
		return moveStack.killed;
	}
	const BlockList& getAllBlocks(SgBlackWhite c) const {
		return blockList[c];
	}

	SgPointSet findInDir(SgPoint from, SgPoint to) const;
	void findInDir(SgPoint from, SgPoint to, SgPointSet& set) const;

	int containsColor(const SgPointSet& set, SgBlackWhite color) const;
	bool allColor(const SgPointSet& set, SgBlackWhite color) const;
	int stage() const;

	int numEmptyPoints() const {
		return state.empty.Size();
	}

	SgPoint getEmptyPoint(int index) const {
		SG_ASSERT(index < numEmptyPoints());
		return state.empty[index];
	}

	float estimateEmptyPts() const;

	float komi() const {
		return setup.getKomi();
	}

	void setKomi(float f) {
		setup.setKomi(f);
	}

	void killBlock(const Block* block);
	int stonesKilled(SgBlackWhite c) {
		return state.numPrisoners[c];
	}

	bool isSuicide(SgPoint p, SgBlackWhite c) const;

	void print() {
		SgDebug() << "----------board played " << numMoves << "\n";
		SgDebug() << "black blocks\n";
		for (BlockList::Iterator bit(blockList[SG_BLACK]); bit; ++bit)
			(*bit).print();
		SgDebug() << "white blocks\n";
		for (BlockList::Iterator bit(blockList[SG_WHITE]); bit; ++bit)
			(*bit).print();
		SgDebug() << "-----------print done\n";
	}

	bool isFill(SgPoint p, SgBlackWhite c) const {
		return numNeigh(p, SgOppBW(c)) == 0 && numEmptyNeigh(p) == 0;
	}

private:

	struct StackEntry {
		Move move;
		Block* addedTo;
		SgArrayList<Block*, 4> killed;
		SgArrayList<SgPoint, 4> newLibs;
		SgArrayList<Block*, 4> merged;
		Block* suicide;
		bool isSingleStone;

		void copy(const StackEntry& s) {
			move.copy(s.move);
			addedTo = s.addedTo;
			suicide = s.suicide;
			isSingleStone = s.isSingleStone;
			//Util::copy(killed, s.killed);
			Util::copy(newLibs, s.newLibs);
			//Util::copy(merged, s.merged);
		}

		void clear() {
			addedTo = 0;
			killed.Clear();
			newLibs.Clear();
			merged.Clear();
			suicide = 0;
			isSingleStone = false;
		}
	};

	struct State {
		SgBlackWhite toPlay;
		SgArray<int, SG_MAXPOINT> color;
		SgBWSet all;
		SgPointSet empty;
		SgArray<Block*, SG_MAXPOINT> blocks;
		SgBWArray<int> numPrisoners;
		SgBWArray<int> numStones;
		SgBWArray<SgArray<int, SG_MAXPOINT> > neighbors;

		/**
		 * the simple-ko rule forbids to play at this point for the next round;
		 */
		SgPoint koBan;

		void copy(const State& s) {
			toPlay = s.toPlay;
			for (int i = 0; i < SG_MAXPOINT; i++)
				color[i] = s.color[i];
			Util::copy(numPrisoners, s.numPrisoners);
			Util::copy(numStones, s.numStones);
			Util::copy(all[SG_BLACK], s.all[SG_BLACK]);
			Util::copy(all[SG_WHITE], s.all[SG_WHITE]);
			Util::copy(empty, s.empty);
			Util::copy(neighbors[SG_BLACK], s.neighbors[SG_BLACK]);
			Util::copy(neighbors[SG_WHITE], s.neighbors[SG_WHITE]);
			koBan = s.koBan;
		}
	};

	Setup setup;
	int numMoves;
	State state;
	//SgArrayList<StackEntry, GO_MAX_NUM_MOVES> moveStack;
	StackEntry moveStack;
	MoveInfo moveInfo;
	//SgArrayList<Block, MAX_BLOCKS> blockList;
	SgBWArray<BlockList> blockList;
	SgBoardConst boardConst;
	static int count;

	Block& createNewBlock(SgBlackWhite c);

	void initBlock(Block& block, SgPoint p, SgBlackWhite player);

	SgArrayList<Block*, 4> getAdjBlocks(SgPoint p) const;

	/**
	 * get the player's adjacent blocks.
	 */
	SgArrayList<Block*, 4> getAdjBlocks(SgPoint p, SgBlackWhite player) const;

	void tryKill(Move m, StackEntry& entry);

	/**
	 * restore the player's blocks killed just now.
	 */
	void restoreKill(Block* block, SgBlackWhite player);

	void addLibToAdjBlocks(SgPoint p, SgBlackWhite opp);
	void removeLibFromAdjBlocks(SgPoint p, SgBlackWhite op);

	void addStone(Move m);
	void removeStone(SgPoint p);

	/**
	 * update blocks after a move;
	 */
	void updateBlocksAfterAdd(Move m, StackEntry& entry);
	void updateBlocksAfterUndo(const StackEntry& entry);
	/**
	 * a move may connect some blocks.
	 */
	void mergeBlocks(Move m, SgArrayList<Block*, 4> blocks);

	void restoreState(const StackEntry& entry);

	void addStoneToBlock(SgPoint p, Block* block, StackEntry& entry);

	bool checkCorner(SgPoint p) const;
	bool checkEdge(SgPoint p) const;
	bool checkSuicide(SgPoint p, StackEntry& entry);
	void setBlock(Block& b);
};

inline Block* Board::anchor(SgPoint p) const {
	Block* b = state.blocks[p];
	//if (b == 0) {
	//	SgDebug() << "anchor " << SgWritePoint(p) << "\n";
	//}
	//SG_ASSERT(b != 0);
	return b;
}

inline SgBlackWhite Board::toPlay() const {
	return state.toPlay;
}

inline bool Board::isPass(SgPoint p) const {
	return (p == SG_PASS || SgMoveUtil::IsCouponMove(p));
}

/**
 * TODO isBorder?
 */
inline bool Board::isValid(SgPoint p) const {
	return SgPointUtil::InBoardRange(p) && !isBorder(p);
}

inline bool Board::isEmpty(SgPoint p) const {
	return state.color[p] == SG_EMPTY;
}

inline int Board::numNeigh(SgPoint p, SgBlackWhite c) const {
	return state.neighbors[c][p];
}

inline int Board::numDiagonal(SgPoint p, SgBoardColor c) const {
	int n = 0;
	if (isColor(p - SG_NS - SG_WE, c))
		++n;
	if (isColor(p - SG_NS + SG_WE, c))
		++n;
	if (isColor(p + SG_NS - SG_WE, c))
		++n;
	if (isColor(p + SG_NS + SG_WE, c))
		++n;
	return n;
}

inline int Board::num8Neigh(SgPoint p, SgBlackWhite player) const {
	return numNeigh(p, player) + numDiagonal(p, player);
}

inline int Board::numEmptyNeigh(SgPoint p) const {
	int i = 0;
	if (isEmpty(p - SG_NS))
		i++;
	if (isEmpty(p - SG_WE))
		i++;
	if (isEmpty(p + SG_WE))
		i++;
	if (isEmpty(p + SG_NS))
		i++;
	return i;
}

inline int Board::numEmptyDiagonal(SgPoint p) const {
	int n = 0;
	if (isEmpty(p - SG_NS - SG_WE))
		++n;
	if (isEmpty(p - SG_NS + SG_WE))
		++n;
	if (isEmpty(p + SG_NS - SG_WE))
		++n;
	if (isEmpty(p + SG_NS + SG_WE))
		++n;
	return n;
}

inline int Board::num8EmptyNeigh(SgPoint p) const {
	return numEmptyDiagonal(p) + numEmptyNeigh(p);
}

inline bool Board::isColor(SgPoint p, int c) const {
	return state.color[p] == c;
}

inline SgBlackWhite Board::getColor(SgPoint p) const {
	return state.color[p];
}

inline bool Board::adjTo(SgPoint p, Block* block) const {
	return state.blocks[p - SG_NS] == block || state.blocks[p - SG_WE] == block
			|| state.blocks[p + SG_WE] == block || state.blocks[p + SG_NS]
			== block;
}

inline SgArrayList<Block*, 4> Board::getAdjBlocks(SgPoint p) const {
	SgArrayList<Block*, 4> result;
	if (numNeigh(p, SG_BLACK) > 0 || numNeigh(p, SG_WHITE) > 0) {
		Block* block;
		if ((block = state.blocks[p - SG_NS]) != 0)
			result.PushBack(block);
		if ((block = state.blocks[p - SG_WE]) != 0 && !result.Contains(block))
			result.PushBack(block);
		if ((block = state.blocks[p + SG_WE]) != 0 && !result.Contains(block))
			result.PushBack(block);
		if ((block = state.blocks[p + SG_NS]) != 0 && !result.Contains(block))
			result.PushBack(block);
	}
	return result;
}

inline int Board::Line(SgPoint p) const {
	return boardConst.Line(p);
}

inline bool Board::isBorder(SgPoint p) const {
	return isColor(p, SG_BORDER);
}

inline int Board::numStones(SgPoint block) const {
	SG_ASSERT(!isEmpty(block));
	return state.blocks[block]->numPoints();
}

inline int Board::numLibs(SgPoint p) const {
	SG_ASSERT(!isEmpty(p));
	SG_ASSERT(isValid(p));
	//	SgBlackWhite c = getColor(p);
	return state.blocks[p]->numLib();
}

inline bool Board::lastMoveSingle() const {
	return moveStack.isSingleStone;
}

inline bool Board::lastMoveMerge() const {
	return moveStack.merged.Length() > 0;
}

inline const SgArrayList<Block*, 4>& Board::getMerged() const {
	return moveStack.merged;
}

inline bool Board::hasNeighbors(SgPoint p, SgBlackWhite c) const {
	return (state.neighbors[c][p] > 0);
}

inline const SgPointSet& Board::LineSet(SgGrid line) const {
	return boardConst.LineSet(line);
}

inline SgGrid Board::pos(SgPoint p) const {
	return boardConst.Pos(p);
}

inline bool Board::hasDiagonals(SgPoint p, SgBoardColor c) const {
	return (isColor(p - SG_NS - SG_WE, c) || isColor(p - SG_NS + SG_WE, c)
			|| isColor(p + SG_NS - SG_WE, c) || isColor(p + SG_NS + SG_WE, c));
}

inline bool Board::hasEmptyNeighbors(SgPoint p) const {
	return state.neighbors[SG_EMPTY][p];
}

inline int Board::size() const {
	return SG_MAX_SIZE;
}

inline const SgPointSet& Board::all(SgBlackWhite color) const {
	return state.all[color];
}

inline bool Board::occupied(SgPoint p) const {
	return (state.blocks[p] != 0);
}

inline bool Board::isLegal(SgPoint p, SgBlackWhite player) const {
	if (isValid(p) && isEmpty(p) && player == state.toPlay && p != state.koBan
			&& !isSuicide(p, player))
		return true;
	else
		return false;
}

inline void Board::findInDir(SgPoint from, SgPoint to, SgPointSet& set) const {
	SgGrid x = SgPointUtil::Row(to) - SgPointUtil::Row(from);
	SgGrid y = SgPointUtil::Col(to) - SgPointUtil::Col(from);
	//	SG_ASSERT(x == SG_WE || x == -SG_WE || x == 0);
	//	SG_ASSERT(y == SG_NS || y == -SG_NS || y == 0);
	SG_ASSERT(!(x == 0 && y == 0));
	SgPoint p1, p2, p3 = to + x * SG_NS + y * SG_WE;
	if (x == 0) {
		p1 = to + SG_NS;
		p2 = to - SG_NS;
	} else if (y == 0) {
		p1 = to + SG_WE;
		p2 = to - SG_WE;
	} else {
		p1 = to + x * SG_WE;
		p2 = to + y * SG_NS;
	}
	if (isValid(p1) && !set.Contains(p1))
		set.Include(p1);
	if (isValid(p2) && !set.Contains(p2))
		set.Include(p2);
	if (isValid(p3) && !set.Contains(p3))
		set.Include(p3);
	//SgDebug() << SgWritePoint(from) << " -> " << SgWritePoint(to) << " dir "
	//		<< SgWritePointSet(set) << "\n";
}

inline SgPointSet Board::findInDir(SgPoint from, SgPoint to) const {
	SgGrid x = SgPointUtil::Row(to) - SgPointUtil::Row(from);
	SgGrid y = SgPointUtil::Col(to) - SgPointUtil::Col(from);
	SgPoint p1, p2, p3 = to + x * SG_NS + y * SG_WE;
	if (x == 0) {
		p1 = to + SG_NS;
		p2 = to - SG_NS;
	} else if (y == 0) {
		p1 = to + SG_WE;
		p2 = to - SG_WE;
	} else {
		p1 = to + x * SG_WE;
		p2 = to + y * SG_NS;
	}
	SgPointSet set;
	if (isValid(p1))
		set.Include(p1);
	if (isValid(p2))
		set.Include(p2);
	if (isValid(p3))
		set.Include(p3);
	if (isValid(p2) && isValid(p3))
		findInDir(p2, p3, set);
	if (isValid(p1) && isValid(p3))
		findInDir(p1, p3, set);
	//SgDebug() << SgWritePoint(from) << " -> " << SgWritePoint(to) << " dir "
	//			<< SgWritePointSet(set) << "\n";
	return set;
}

inline int Board::containsColor(const SgPointSet& set, SgBlackWhite color) const {
	int count = 0;
	for (SgSetIterator sit(set); sit; ++sit)
		if (isColor(*sit, color))
			count++;
	return count;
}

inline bool Board::allColor(const SgPointSet& set, SgBlackWhite color) const {
	for (SgSetIterator sit(set); sit; ++sit)
		if (!isColor(*sit, color))
			return false;
	return true;
}

inline bool Board::hasNeigh8(SgPoint p, SgBlackWhite c) const {
	return hasNeighbors(p, c) || hasDiagonals(p, c);
}

inline int Board::stage() const {
	if (numMoves <= 8)
		return START;
	else if (numMoves <= 100)
		return CLIMAX;
	else
		return DENOUMONE;
}

inline int Board::getColor(int x, int y) const {
	SgPoint p = SgPointUtil::Pt(x, y);
	return getColor(p);
}

inline bool Board::lastMoveInfo(GoMoveInfoFlag flag) const {
	return moveInfo.test(flag);
}

inline bool Board::isSuicide(SgPoint p, SgBlackWhite toPlay) const {
	if (numEmptyNeigh(p) > 0)
		return false;
	SgBlackWhite opp = SgOppBW(toPlay);
	for (SgNb4Iterator it(p); it; ++it) {
		if (isBorder(*it))
			continue;
		SgEmptyBlackWhite c = getColor(*it);
		if (c == toPlay && numLibs(*it) > 1)
			return false;
		if (c == opp && numLibs(*it) == 1)
			return false;
	}
	return true;
}

#endif /* BOARD_H_ */

